package com.Oct_Eight;

import java.util.Arrays;

/**
 * 870. 优势洗牌
 * 给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
 *
 * 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/advantage-shuffle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/08 21:37
 */

public class Solution870 {
    /**
     * 双指针加贪心
     * @param nums1
     * @param nums2
     * @return
     */

    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n=nums1.length,minIndex=0;
        Arrays.sort(nums1);
        boolean[] vis=new boolean[n];
        int[] ans=new int[n];
        for (int i=0;i<n;i++)
        {
            int left=0,right=n;
            while (left<right)
            {
                int mid=left+((right-left)>>1);
                if (nums1[mid]<nums2[i])
                {
                    left=mid+1;
                }else
                {
                    right=mid;
                }
            }
            while (left<n&&(vis[left]||nums1[left]==nums2[i])) left++;
            if (left==n)
            {
                while(vis[minIndex])
                {
                    minIndex++;
                }
                ans[i]=nums1[minIndex];
                vis[minIndex++]=true;
            }else
            {
                vis[left]=true;
                ans[i]=nums1[left];
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Solution870 solution870=new Solution870();
        System.out.println(Arrays.toString(solution870.advantageCount(new int[]{12,24,8,32}, new int[]{13,25,32,11})));
    }
}
